package codetop.microsoft.T143;

import util.ListNode;

/**
 * @Author: 18362
 * @Create: 2022-09-07 16:03:49 星期三
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null)
            return;
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode tail = reverse(slow.next);
        slow.next = null;
        ListNode p = head, q = tail;
        while (p != null && q != null) {
            ListNode t = p.next;
            p.next = q;
            q = q.next;
            p.next.next = t;
            p = t;
        }
    }

    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode tHead = reverse(head.next);
        ListNode tail = head.next;
        head.next = null;
        tail.next = head;
        return tHead;
    }
}